package com.atcumt.QiAnXin;

import com.atcumt.Carl.LinkedList.ListNode;

public class OKLink {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        // write code here
        ListNode dummy = new ListNode(-1, head);
        ListNode fast = dummy, slow = dummy;
        while (n-- > 0) {
            fast = fast.next;
        }
        while (fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }

    public boolean wordPattern(String pattern, String str) {
        // write code here
        str = str.replaceAll(" ", "");
        if (str.length() == 0) {
            if (pattern.length() != 0) {
                for (int i = 1; i < pattern.length(); i++) {
                    if (pattern.charAt(i - 1) != pattern.charAt(i)) {
                        return false;
                    }
                }
                return false;
            }
            return true;
        }
        if (pattern.length() == 0) {
            return false;
        }
        if (pattern.length() == 1) {
            return true;
        }

        char a = pattern.charAt(0);
        int ca = 0;
        int cb = 0;
        for (int i = 0; i < pattern.length(); i++) {
            if (pattern.charAt(i) == a) {
                ca++;
            } else {
                cb++;
            }
        }

        int lv = str.length();
        int lp = pattern.length();
        if (cb == 0) {
            if (lv % ca != 0) {
                return false;
            }
            int la = lv / ca;
            String aa = str.substring(0, la);
            for (int i = aa.length(); i < str.length(); i += aa.length()) {
                if (!str.substring(i, i + aa.length()).equals(aa)) {
                    return false;
                }
            }
            return true;
        }

        for (int la = 0; la * ca <= str.length(); ++la) {
            int rest = lv - ca * la;
            if (rest % cb != 0) {
                continue;
            }

            int lb = rest / cb;
            int ci = 0;
            boolean isMatch = true;
            String aa = "", bb = "";

            for (char c : pattern.toCharArray()) {
                if (c == a) {
                    String cur = str.substring(ci, ci += la);
                    if (aa.length() == 0) {
                        aa = cur;
                    } else if (!aa.equals(cur)) {
                        isMatch = false;
                        break;
                    }

                } else {
                    String cur1 = str.substring(ci, ci += lb);
                    if (bb.length() == 0) {
                        bb = cur1;
                    } else if (!bb.equals(cur1)) {
                        isMatch = false;
                        break;
                    }
                }
            }
            if (isMatch && !aa.equals(bb)) {
                return true;
            }
        }
        return false;
    }
}
